#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int ans = 0;
        int len = coins.size();
        int l = 0;
        int r = 0;
        int cnt = 0;
        while (r < target) {
            if (cnt >= len) {
                ans++;
                r = r + r + 1;
                continue;
            }
            if (coins[cnt] == r + 1) {
                cnt++;
                r = r + r + 1;
            }
            else {
                int r1 = r + coins[cnt];
                if (coins[cnt] > r) {
                    r = r + r + 1;
                    ans++;
                }
                else {
                    r = r1;
                    cnt++;
                }
            }
            // cout<<maxtager<<" "<<r<<" "<<coins[cnt]<<endl;
        }
        return ans;
    }
};